{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Maximum Number of Marked Indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumOfMarkedIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求出最多标记下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>一开始，所有下标都没有被标记。你可以执行以下操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个 <strong>互不相同且未标记</strong>&nbsp;的下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，满足&nbsp;<code>2 * nums[i] &lt;= nums[j]</code>&nbsp;，标记下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你执行上述操作任意次，返回<em>&nbsp;</em><code>nums</code>&nbsp;中最多可以标记的下标数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,5,2,4]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] &lt;= nums[1] ，标记下标 2 和 1 。\n",
    "没有其他更多可执行的操作，所以答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [9,2,5,4]\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] &lt;= nums[0] ，标记下标 3 和 0 。\n",
    "第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] &lt;= nums[2] ，标记下标 1 和 2 。\n",
    "没有其他更多可执行的操作，所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [7,6,8]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>没有任何可以执行的操作，所以答案为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-maximum-number-of-marked-indices](https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-maximum-number-of-marked-indices](https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,2,4]', '[9,2,5,4]', '[7,6,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        print(n)\n",
    "        vis = [False] * n\n",
    "        left = n//2-1\n",
    "        right = n - 1\n",
    "        ans = 0\n",
    "        while left >= 0:\n",
    "            if vis[right]:\n",
    "                right -= 1\n",
    "                if left == right:\n",
    "                    left -= 1\n",
    "            elif (2 * nums[left]) <= nums[right]:\n",
    "                print(left,right,nums[left],nums[right])\n",
    "                ans += 2\n",
    "                vis[left] = True\n",
    "                right -= 1\n",
    "                left -= 1\n",
    "            else:\n",
    "                left -= 1\n",
    "        # print(left,right)\n",
    "        # print(nums)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = (len(nums)+1)//2\n",
    "        while right<len(nums):\n",
    "            if nums[left]*2<=nums[right]:\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return left*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def check(k):\n",
    "            return not all(a * 2 <= b for a, b in zip(nums[:k], nums[len(nums) - k:]))\n",
    "        \n",
    "        return bisect_right(range(1, len(nums) // 2 + 1), False, key = check) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        i = 0\n",
    "        for x in nums[(n + 1) // 2:]:\n",
    "            if x >= nums[i] * 2:\n",
    "                i += 1\n",
    "        \n",
    "        return i * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        #从最大的一半中尽可能地找到能匹配的\n",
    "        i = 0\n",
    "        for x in nums[(len(nums)+1)//2:]: # 奇数个中间的不参与匹配\n",
    "            if nums[i]*2<=x:\n",
    "                i += 1\n",
    "        return i*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for right in range(math.ceil(n / 2), n):\n",
    "            if 2 * nums[left] <= nums[right]:\n",
    "                right += 1\n",
    "                left += 1\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1  # 开区间\n",
    "        while left + 1 < right:\n",
    "            k = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i, j = n // 2 - 1, n - 1\n",
    "        while i >= 0 and i < j:\n",
    "            if 2 * nums[i] <= nums[j]:\n",
    "                ans += 2\n",
    "                j -= 1\n",
    "            i -= 1\n",
    "        return ans\n",
    "            \n",
    "# [42,83,48,10,24,55,9,100,10,17,17,99,51,32,16,98,99,31,28,68,71,14,64,29,15,40]\n",
    "# 26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        # 2,3,4,5\n",
    "        nums.sort()\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums) // 2\n",
    "        ans = 0\n",
    "        while left < len(nums) // 2 and right < len(nums):\n",
    "            if nums[left] * 2 <= nums[right]:\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                right += 1\n",
    "        \n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        h = n // 2\n",
    "        k = h\n",
    "        res = 0\n",
    "        for i in range(h):\n",
    "            while k < n and nums[k] < nums[i] * 2:\n",
    "                k += 1\n",
    "            if k < n:\n",
    "                res += 2\n",
    "                k += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "如果要标记的尽量多\n",
    "应该考虑相近的去标记？\n",
    "\n",
    "或者从小到大来看，nums[i]对应的所有下标都找到，然后去最低的标记，也就是找到lower bound\n",
    "nums[0]最小，那么nums[0]对应的nums[j0]应该是i的上限，i不能超过j0\n",
    "直到i_n对应的两倍j_n被biesct找出来是n，那么就结束了，\n",
    "\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1\n",
    "        while left + 1 < right:\n",
    "            k = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        ans,left,right=0,bisect_right(nums,nums[-1]/2)-1,length-1\n",
    "        left = length//2-1 if left>=length//2-1 else left\n",
    "        init_left = left\n",
    "        while left>=0 and right>init_left:\n",
    "            if nums[left]*2<=nums[right]:\n",
    "                right-=1\n",
    "                left-=1\n",
    "                ans +=2\n",
    "            else:\n",
    "                break\n",
    "            while left>0 and nums[left]*2>nums[right]:\n",
    "                left -=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res=0\n",
    "        i=0\n",
    "        j=len(nums)//2\n",
    "        while j<len(nums) and i<len(nums)//2:\n",
    "            if nums[j]>=nums[i]*2:\n",
    "                res+=1\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return res*2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        # 1. 二分答案\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1 # 开区间\n",
    "        while left + 1 < right:\n",
    "            k = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left * 2\n",
    "        # 2. 双指针\n",
    "        # nums.sort()\n",
    "        # i = 0\n",
    "        # for x in nums[(len(nums) + 1) // 2]:\n",
    "        #     if nums[i] * 2 <= x:\n",
    "        #         i += 1\n",
    "        # return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        res = 0\n",
    "        # print(nums)\n",
    "        j = n // 2\n",
    "        for i in range(n // 2):\n",
    "            while j < n and nums[j] < 2 * nums[i]:\n",
    "                j += 1\n",
    "            if j != n:\n",
    "                res += 2\n",
    "                # print(i, j, nums[i], nums[j])\n",
    "            else:\n",
    "                break\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k: int)->bool:\n",
    "            return all(nums[i] * 2 <= nums[n-k+i] for i in range(k))\n",
    "\n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l + l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        left = 0\n",
    "        right = n // 2\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            flag = True\n",
    "            for index in range(mid):\n",
    "                if nums[index] + nums[index] > nums[index - mid]:\n",
    "                    flag = False\n",
    "                    break\n",
    "\n",
    "            if flag:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left + left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = n//2\n",
    "        if n % 2 == 0:\n",
    "            left -= 1\n",
    "        mid = left\n",
    "        right = n - 1\n",
    "        while left >= 0 and right > mid:\n",
    "            if 2 * nums[left] <= nums[right]:\n",
    "                left -= 1\n",
    "                right -= 1\n",
    "                ans += 2\n",
    "            else:\n",
    "                left -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        left, right = 0, n // 2 + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - mid] for i in range(mid)):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        # 1. 二分答案\n",
    "        # nums.sort()\n",
    "        # left, right = 0, len(nums) // 2 + 1 # 开区间\n",
    "        # while left + 1 < right:\n",
    "        #     k = (left + right) // 2\n",
    "        #     if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "        #         left = k\n",
    "        #     else:\n",
    "        #         right = k\n",
    "        # return left * 2\n",
    "        # 2. 双指针\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2 \n",
    "        # 模拟： 数对数目： 2*nums[i] <= nums[j], 求下标数\n",
    "        # 二分：\n",
    "        # nums.sort()\n",
    "        # left, right = 0, len(nums) // 2 + 1\n",
    "        # while left + 1 < right:\n",
    "        #     k = (left + right) // 2\n",
    "        #     if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "        #         left = k\n",
    "        #     else:\n",
    "        #         right = k \n",
    "        # return left * 2 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        for x in nums[(len(nums)+1)//2:]:\n",
    "            if x>=2*nums[i]:\n",
    "                i+=1\n",
    "        return 2*i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def check(mid):\n",
    "            for i in range(mid):\n",
    "                if nums[i]*2>nums[-mid+i]:return False\n",
    "            return True\n",
    "\n",
    "        left,right=0,n//2\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid+1\n",
    "            else:right=mid-1\n",
    "        return right*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1  # 开区间\n",
    "\n",
    "        while left + 1 < right:\n",
    "            # left == right\n",
    "            k = (left + right) // 2\n",
    "            # n - k + i => i - k \n",
    "            # python index\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        \n",
    "        return left * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        n_2 = n >> 1\n",
    "        left = n_2-1\n",
    "        right = n - 1\n",
    "        ans = 0\n",
    "        while left >= 0:# and right >= n_2:\n",
    "            if (2 * nums[left]) <= nums[right]:\n",
    "                ans += 2\n",
    "                right -= 1\n",
    "            left -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1  # 开区间\n",
    "        while left + 1 < right:\n",
    "            k = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        i = 0\n",
    "        for x in nums[(n+1) // 2:]:\n",
    "            if x >= 2 * nums[i]:\n",
    "                i += 1\n",
    "        \n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = (n >> 1)-1\n",
    "        right = n - 1\n",
    "        ans = 0\n",
    "        while left >= 0: # and right >= n_2:\n",
    "            if (2 * nums[left]) <= nums[right]:\n",
    "                ans += 2\n",
    "                right -= 1\n",
    "            left -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = (n - 1) // 2\n",
    "        right = n - 1\n",
    "        while left >= 0 and right > (n - 1) // 2:\n",
    "            if 2 * nums[left] <= nums[right]:\n",
    "                left -= 1\n",
    "                right -= 1\n",
    "                ans += 2\n",
    "            else:\n",
    "                left -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        # 贪心,nums[i]越小，那么对于nums[j]的要求也越低\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n//2+1\n",
    "        while left + 1 < right:\n",
    "            k = (left+right)//2\n",
    "            if all(nums[i]*2 <=  nums[i-k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left*2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        r = (n + 1) // 2\n",
    "        l = 0\n",
    "        while r < n:\n",
    "            if 2 * nums[l] <= nums[r]:\n",
    "                res += 2\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(n + 1)//2:]:\n",
    "            if x >= nums[i] * 2:\n",
    "                i += 1\n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k: int)->bool:\n",
    "            if k == 0:\n",
    "                return True\n",
    "            return all(x * 2 <= y for x, y in zip(nums[:k], nums[-k:]))\n",
    "                       \n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l + l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k):\n",
    "            if all(nums[i]*2<=nums[n-k+i] for i in range(k)):\n",
    "                return True\n",
    "        \n",
    "        # ans = 2 * bisect_left(range(0, n//2+1), True, key=check)\n",
    "        ans = 0\n",
    "        left, right = -1, n//2+1\n",
    "        while left+1<right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        ans = left * 2\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = (n - 1) // 2\n",
    "        mid = left\n",
    "        right = n - 1\n",
    "        while left >= 0 and right > mid:\n",
    "            if 2 * nums[left] <= nums[right]:\n",
    "                left -= 1\n",
    "                right -= 1\n",
    "                ans += 2\n",
    "            else:\n",
    "                left -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if all(nums[i] * 2 <= nums[n - mid + i] for i in range(mid)):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        right_start = n//2 if n%2==0 else (n//2+1)\n",
    "        left = 0\n",
    "        print(right_start)\n",
    "        for right,x in enumerate(nums[right_start:]):\n",
    "            if 2*nums[left] <= x:\n",
    "                left+=1\n",
    "                ans += 1\n",
    "        return ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        # 这里的k表示个数\n",
    "        def check(k):\n",
    "            for i in range(k):\n",
    "                if not 2 * nums[i] <= nums[n - k + i]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = n//2\n",
    "        for j in range(n//2):\n",
    "            while i < n and 2*nums[j] > nums[i]:\n",
    "                i += 1\n",
    "            if i < n:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        i = 0\n",
    "        for x in nums[(n + 1) // 2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if all(nums[i] * 2 <= nums[n-mid+i] for i in range(mid)):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l + l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # def check(k):\n",
    "        #     if all(nums[i]*2<=nums[i-k] for i in range(k)):\n",
    "        #         return True\n",
    "        #     return False\n",
    "        \n",
    "        # ans = 0\n",
    "        # left, right = -1, n//2+1\n",
    "        # while left+1<right:\n",
    "        #     mid = (left+right) // 2\n",
    "        #     if check(mid):\n",
    "        #         left = mid\n",
    "        #     else:\n",
    "        #         right = mid\n",
    "        # ans = left * 2\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        i = 0\n",
    "        for x in nums[(n+1)//2:]:\n",
    "            if nums[i] * 2 <= x:\n",
    "                i += 1\n",
    "        return i * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        m = len(nums)\n",
    "        res = 0\n",
    "        i = m - 1\n",
    "        right = m // 2 - 1\n",
    "        while i > right:\n",
    "            current = nums[i] / 2\n",
    "            left = 0\n",
    "            while left < right:\n",
    "                middle = (left + right + 1) // 2\n",
    "                if nums[middle] > current:\n",
    "                    right = middle - 1\n",
    "                else:\n",
    "                    left = middle\n",
    "            if nums[left] <= current:\n",
    "                res += 2\n",
    "            # print(current, nums[left], left)\n",
    "            if left == 0:\n",
    "                break\n",
    "            right = left - 1\n",
    "            i -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left,right = 0, len(nums)//2+1 #开区间\n",
    "        while left+1 < right:\n",
    "            k = (left+right)//2\n",
    "            if all(nums[i]*2 <= nums[i-k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        r = n // 2\n",
    "        ans = 0\n",
    "        for i in range(0, n//2) :\n",
    "            while r < n and nums[i] * 2 > nums[r] :\n",
    "                r += 1\n",
    "            if r < n :\n",
    "                r += 1\n",
    "                ans += 2\n",
    "            else :\n",
    "                break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k: int)->bool:\n",
    "            if k == 0:\n",
    "                return True\n",
    "            r = k\n",
    "            for i in range(k):\n",
    "                while r < n and nums[i] * 2 > nums[r]:\n",
    "                    r += 1\n",
    "                if r == len(nums) or k - i > n - r:\n",
    "                    return False\n",
    "                r += 1\n",
    "            return True\n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = 0,(n+1)//2\n",
    "        while r<n:\n",
    "            if 2*nums[l]<=nums[r]:\n",
    "                ans+=2\n",
    "                l+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left,right=0,len(nums)//2+1\n",
    "        while(left+1<right):\n",
    "            k=(left+right)//2\n",
    "            if all(nums[i]*2<=nums[i-k] for i in range(k)):\n",
    "                left=k\n",
    "            else:\n",
    "                right=k\n",
    "        return left*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k: int)->bool:\n",
    "            if k == 0:\n",
    "                return True\n",
    "            for x, y in zip(nums[:k], nums[-k:]):\n",
    "                if x * 2 > y:\n",
    "                    return False\n",
    "            return True\n",
    "        l, r = 0, n // 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l + l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        i = 0\r\n",
    "        for x in nums[(len(nums) + 1) // 2:]:\r\n",
    "            if nums[i] * 2 <= x:\r\n",
    "                i += 1\r\n",
    "        return i * 2\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = 1\n",
    "        r = n >> 1\n",
    "        while l <= r:\n",
    "            m = l + r >> 1\n",
    "            right = m\n",
    "            for i in range(m):\n",
    "                k = nums[i] << 1\n",
    "                while right < n and nums[right] < k:\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    r = m - 1\n",
    "                    break\n",
    "                right += 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return r * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        # 选择标记\n",
    "        # nums.sort()\n",
    "        # ans = 0\n",
    "        # checked = [False] * len(nums)\n",
    "        # for i in range(len(nums)):\n",
    "        #     for j in range(i,len(nums)):\n",
    "        #         if not checked[j] and 2 * nums[i] <= nums[j]:\n",
    "        #             ans += 2\n",
    "        #             checked[j] = True\n",
    "        #             break\n",
    "        # return ans\n",
    "        nums = sorted(nums,reverse= True)\n",
    "        nums_2 = nums.copy()\n",
    "        ans = 0\n",
    "        s = []\n",
    "        n = len(nums)\n",
    "        for i in range((n+1)//2,n):\n",
    "            if 2 * nums_2[i] <= nums[ans]:\n",
    "                ans += 1\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) // 2 + 1  # 开区间\n",
    "        while left + 1 < right:\n",
    "            k = (left + right) // 2\n",
    "            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):\n",
    "                left = k\n",
    "            else:\n",
    "                right = k\n",
    "        return left * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = n // 2\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2 + 1 \n",
    "            if any(nums[idx] * 2 > nums[n + idx - mid] for idx in range(mid)):\n",
    "                r = mid - 1 \n",
    "            else:\n",
    "                l = mid \n",
    "        return 2 * l \n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def key(k):\n",
    "            if k * 2 > n:\n",
    "                return False\n",
    "            for i in range(k):\n",
    "                if nums[i] * 2 <= nums[n-k+i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        lo, hi = 0, n\n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if key(mi):\n",
    "                lo = mi + 1\n",
    "            else:\n",
    "                hi = mi\n",
    "        return (lo-1) * 2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
